from collections import defaultdict
import time
from typing import Dict, Set, Tuple
class Relation(object):
    def __init__(self, pairs: Set[Tuple[str, str]]):
        self.images = defaultdict(set)  # type: Dict[str, Set[str]]
        self.preimages = defaultdict(set)  # type: Dict[str, Set[str]]
        self.intent_map = {}  # 用于存储以内涵（frozenset）为键的概念

        for x, y in pairs:
            self.add(x, y)

    def add(self, x: str, y: str) -> None:
        self.images[x].add(y)
        self.preimages[y].add(x)

    def remove(self, x: str, y: str) -> None:
        if y in self.images[x]:
            self.images[x].remove(y)
        if x in self.preimages[y]:
            self.preimages[y].remove(x)

    def image(self, x: str) -> Set[str]:
        return self.images.get(x, set())

    def preimage(self, y: str) -> Set[str]:
        return self.preimages.get(y, set())

    def add_concept(self, concept: 'Concept') -> None:
        self.intent_map[concept.intent] = concept  # 使用 frozenset 作为键存储概念


class Concept(object):
    def __init__(self, extent, intent):
        self.extent = frozenset(extent)  # 确保外延是不可变集合
        self.intent = frozenset(intent)  # 确保内涵是不可变集合
        self.doIntent = None
        self.MaximalConcept = None
        self.NewConcept = None
        self.visited = None

    def __hash__(self):
        return hash((self.extent, self.intent))

    def __eq__(self, other):
        return self.extent == other.extent and self.intent == other.intent

    def __repr__(self):
        # 处理外延和内涵为空的情况，确保按字母顺序排序，并添加引号
        extent_str = '.'.join(sorted(self.extent)) if self.extent else ''
        intent_str = '.'.join(sorted(self.intent)) if self.intent else ''
        return "('{}', '{}')".format(extent_str, intent_str)


class Lattice(object):
    def __init__(self, links):
        self.concepts = set()
        self._relation = Relation([])  # 用于存储父子关系
        for a, b in links:
            self.add_concept(a)
            self.add_concept(b)
            self.add_link(a, b)

    def parents(self, concept):
        return self._relation.preimage(concept)

    def children(self, concept):
        return self._relation.image(concept)

    def add_concept(self, concept):
        self.concepts.add(concept)
        self._relation.add_concept(concept)  # Add concept to the relation

    def top(self):
        concept = next(iter(self.concepts))
        parents = self.parents(concept)
        while len(parents) > 0:
            concept = next(iter(parents))
            parents = self.parents(concept)
        return concept

    def bottom(self):
        concept = next(iter(self.concepts))
        children = self.children(concept)
        while len(children) > 0:
            concept = next(iter(children))
            children = self.children(concept)
        return concept

    def add_link(self, parent, child):
        self._relation.add(parent, child)

    def remove_link(self, parent, child):
        self._relation.remove(parent, child)

    def replace_concept(self, concept, new_concept):
        parents = self.parents(concept)
        children = self.children(concept)
        self.concepts.remove(concept)
        self.add_concept(new_concept)
        for parent in set(parents):
            self.remove_link(parent, concept)
            self.add_link(parent, new_concept)
        for child in set(children):
            self.remove_link(concept, child)
            self.add_link(new_concept, child)

    def __repr__(self):
        return repr(self._relation.images)


def get_closure_concept(intent: frozenset, generator_concept: Concept, lattice: Lattice) -> Concept:
    # 确保 intent 是 frozenset 类型
    if isinstance(intent, set):
        intent = frozenset(intent)

    # 检查是否在 intent_map 中
    if intent in lattice._relation.intent_map:
        return lattice._relation.intent_map[intent]

    # 获取父节点
    parents = lattice.parents(generator_concept)
    for parent in parents:
        if intent <= parent.intent:
            generator_concept = parent
    return generator_concept



def make_new_parents(parents, candidate):
    new_parents = set(parents)
    add_concept = True
    for concept in parents:
        if candidate.intent <= concept.intent:
            add_concept = False
            break
        elif concept.intent <= candidate.intent:
            new_parents.remove(concept)
    if add_concept:
        new_parents.add(candidate)
    return new_parents


def fast_add_intent(intent: frozenset, generator_concept: Concept, lattice: Lattice, obj: str) -> Concept:
    # 确保generator_concept被标记
    if generator_concept.doIntent is None:
        generator_concept.doIntent = intent
        generator_concept.MaximalConcept = generator_concept

    # 获取最小概念
    generator_concept = get_closure_concept(intent, generator_concept, lattice)

    # 如果已经找到概念，直接返回
    if generator_concept.intent == intent:
        return generator_concept

    # 获取该概念的所有父节点作为候选节点
    generator_parents = list(lattice.parents(generator_concept))
    new_parents = set()

    # 遍历父节点，筛选符合条件的父节点
    for candidate in generator_parents:
        if intent <= candidate.intent:
            new_parents = make_new_parents(new_parents, candidate)
        else:
            candidate_new_concept = fast_add_intent(intent, candidate, lattice, obj)
            new_parents = make_new_parents(new_parents, candidate_new_concept)

    # 创建新概念并添加到格中
    new_concept = Concept(generator_concept.extent.union({obj}), intent)

    # 确保概念不重复
    if new_concept not in lattice.concepts:
        lattice.add_concept(new_concept)

    # 维护新概念与父节点的关系
    for parent in new_parents:
        lattice.remove_link(parent, generator_concept)
        lattice.add_link(parent, new_concept)

    lattice.add_link(new_concept, generator_concept)

    return new_concept

def create_lattice_incrementally(G, M, I):
    bottom = Concept(set(), frozenset(M))
    lattice = Lattice([])

    lattice.add_concept(bottom)

    for obj in G:
        intent = I.image(obj)
        concept = fast_add_intent(intent, bottom, lattice, obj)

        # 确保不会添加重复概念
        if concept not in lattice.concepts:
            lattice.add_concept(concept)

    return lattice



# 从文件读取关系数据
def read_relation_from_file(file_path):
    with open(file_path, 'r') as f:
        lines = f.readlines()

    num_objects, num_attributes = map(int, lines[0].strip().split(','))
    relation_pairs = []
    for obj_idx, line in enumerate(lines[1:num_objects + 1]):
        attributes = list(map(int, line.strip().split(',')))
        for attr_idx, has_attr in enumerate(attributes):
            if has_attr == 1:
                relation_pairs.append((str(obj_idx + 1), chr(ord('a') + attr_idx)))

    return num_objects, num_attributes, relation_pairs


# 主函数：用于执行算法
if __name__ == '__main__':
    start = time.time()

    # 示例文件路径
    file_path = '../txt/demo4.txt'
    # file_path = '../experiment04/car.txt'
    num_objects, num_attributes, relation_pairs = read_relation_from_file(file_path)
    rel = Relation(relation_pairs)

    # 自动生成对象数组名和属性数组名
    object_names = ['{}'.format(i + 1) for i in range(num_objects)]
    attribute_names = ['{}'.format(chr(97 + i)) for i in range(num_attributes)]

    # 创建增量概念格
    lattice = create_lattice_incrementally(object_names, attribute_names, rel)

    # 打印概念格结果
    # print("Concept lattice:")
    print(lattice.concepts)
    print(len(lattice.concepts))

    # 输出执行时间
    print("Execution time:", time.time() - start)
